package com.datastructure.test.sortlistnode;

public class SortedListNode {

    public static void main(String[] args) {
        //-426572,-406609,724427,-157789,-132713
        ListNode listNode = new ListNode(-426572);
        listNode.next=new ListNode(-406609);
        listNode.next.next=new ListNode(724427);
        listNode.next.next.next=new ListNode(-157789);
        listNode.next.next.next.next=new ListNode(786521);
        SortedListNode sortedListNode = new SortedListNode();
        sortedListNode.sortInList(listNode);
    }

    public ListNode sortInList (ListNode head) {
        // write code here
        if(head.next==null){
            return head;
        }
        ListNode temp=null;
        ListNode cur = null;
        while (head!=null){
            if(cur==null){
                cur=new ListNode(head.val);
                cur.next=temp;
            } else {
                cur=insertSortedListNode(cur,new ListNode(head.val));
            }
            head=head.next;
        }
        return cur;
    }

    private ListNode insertSortedListNode(ListNode cur, ListNode target) {
        ListNode temp = cur;
        ListNode lastListNode = null;
        while (cur!=null){
            if(target.val<= cur.val){
                if(lastListNode==null){
                    target.next=cur;
                    return target;
                } else {
                    target.next=lastListNode.next;
                    lastListNode.next=target;
                    return temp;
                }
            } else {
                if(cur.next==null){
                    cur.next=target;
                    return temp;
                }
            }
            lastListNode=cur;
            cur=cur.next;
        }
        return temp;
    }
}

class ListNode {
   int val;
   ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}
